import java.util.ArrayList;
import java.util.List;

/**
 * Created by jack on 18/3/26.
 */
public class NQueens {
    private List<List<String>> solvelist  = new ArrayList<>();
    //使用1代表了当前位置存在一个queen
    private int[][] board;
    private int n;

    String queen = "Q";
    String noQueen = ".";
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        board = new int[n][n];
        solve(0);
        return solvelist;
    }

    private void solve(int index){
        if(index == n){
            System.out.println("find one");
            board2string();
        }else{
            //index < n  处理逻辑
            for(int i = 0 ; i < n ; i ++){
                if(checklegal(i,index)){
                    solve(index + 1);
                }
                board[i][index] = 0;
            }
            return;
        }
    }


    //TODO:检查逻辑错误
    private boolean checklegal(int x,int y){
        //检查正上方，左上方，右上方三个方向
        //正上方
        for(int i = 0; i < y; i++){
            if(board[x][i] == 1){
                return false;
            }
        }
        //左上方
        int min = Math.min(x,y);
        for(int i = 0 ; i < min ; i++){
            if(board[x - i -1][y - i -1] == 1){
                return false;
            }
        }
        //右上方
        min = Math.min(y, n - x -1);
        for(int i = 0; i < min ; i++){
            if(board[x + i + 1][y - 1 - i] == 1){
                return false;
            }
        }
        board[x][y] = 1;
        return true;
    }


    void board2string(){
        List<String> oneboard = new ArrayList<>();
        solvelist.add(oneboard);
        for(int i = 0 ; i < n ; i++){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < n; j++){
                sb.append(board[i][j] == 1 ? queen : noQueen);
            }
            oneboard.add(sb.toString());
        }
    }

    public static void main(String[] args) {
        List<List<String>> lists = new NQueens().solveNQueens(5);
        System.out.println("end");
    }
}
